{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Numbers With Same Consecutive Differences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numsSameConsecDiff"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连续差相同的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>返回所有长度为 <code>n</code> 且满足其每两个连续位上的数字之间的差的绝对值为 <code>k</code> 的<strong> 非负整数 </strong>。</p>\n",
    "\n",
    "<p>请注意，<strong>除了 </strong>数字 <code>0</code> 本身之外，答案中的每个数字都 <strong>不能 </strong>有前导零。例如，<code>01</code> 有一个前导零，所以是无效的；但 <code>0</code>&nbsp;是有效的。</p>\n",
    "\n",
    "<p>你可以按 <strong>任何顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 7\n",
    "<strong>输出：</strong>[181,292,707,818,929]\n",
    "<strong>解释：</strong>注意，070 不是一个有效的数字，因为它有前导零。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 1\n",
    "<strong>输出：</strong>[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 0\n",
    "<strong>输出：</strong>[11,22,33,44,55,66,77,88,99]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 2\n",
    "<strong>输出：</strong>[13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 9</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [numbers-with-same-consecutive-differences](https://leetcode.cn/problems/numbers-with-same-consecutive-differences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [numbers-with-same-consecutive-differences](https://leetcode.cn/problems/numbers-with-same-consecutive-differences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n7', '2\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        self.res = []\n",
    "        for i in range(1,10):\n",
    "            self.back_tracing(i,n,k,1)\n",
    "        return self.res\n",
    "    # back trace\n",
    "    # start from 0 and chose next digit\n",
    "    \n",
    "\n",
    "    def back_tracing(self,integer,n,k,l):\n",
    "        if l == n:\n",
    "            self.res.append(integer)\n",
    "            return\n",
    "        last_digit = integer%10\n",
    "        for i in range(10):\n",
    "            if abs(i-last_digit)==k:\n",
    "                x = integer*10+i\n",
    "                self.back_tracing(x,n,k,l+1)\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N, K):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(v, p, n):\n",
    "            if N == n:\n",
    "                return {v}\n",
    "\n",
    "            u = [x for x in [p + K, p-K] if 0 <= x < 10]\n",
    "            ans = set()\n",
    "            for x in u:\n",
    "                ans |= dfs(v * 10 + x, x, n + 1)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        ans = set()\n",
    "        for i in range(1, 10):\n",
    "            ans |= dfs(i, i, 1)\n",
    "        if N == 1:\n",
    "            ans.add(0)\n",
    "        return list(sorted(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N, K):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def generate(N, K):\n",
    "            if N == 1:\n",
    "                return range(1,10)\n",
    "            ans = generate(N-1, K)\n",
    "            new_ans = []\n",
    "            for val in ans:\n",
    "                last = val % 10\n",
    "                if last - K >= 0 and last - K <= 9: \n",
    "                    new_ans.append(val*10+last-K)\n",
    "                if last + K >= 0 and last + K <= 9:\n",
    "                    new_ans.append(val*10+last+K)\n",
    "            return [val for val in set(new_ans)]\n",
    "        if N == 1:\n",
    "            return [val for val in range(0, 10)]\n",
    "        else:\n",
    "            return generate(N,K)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N, K):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if N == 1:\n",
    "            return [0,1,2,3,4,5,6,7,8,9]\n",
    "        \n",
    "        res = list()\n",
    "        for i in range(1, 10):\n",
    "            if i + K < 10 or i - K >= 0:\n",
    "                res.append([i])\n",
    "\n",
    "        for i in range(1, N):\n",
    "            tmp_res = list()\n",
    "            while res:\n",
    "                num = res.pop(0)\n",
    "                tmp_num1, tmp_num2 = num[-1], num[-1]\n",
    "                if tmp_num1 + K < 10:\n",
    "                    tmp_res.append(num+[tmp_num1+K])\n",
    "                    \n",
    "                if tmp_num2 - K >= 0:\n",
    "                    tmp_res.append(num+[tmp_num2-K])   \n",
    "            res = tmp_res\n",
    "         \n",
    "        ret = set()\n",
    "        for i in res:\n",
    "            num = 0\n",
    "            for j, k in enumerate(i):\n",
    "                num += k*10**(N-j-1)\n",
    "                \n",
    "            ret.add(num)\n",
    "            \n",
    "        return list(ret)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N, K):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        \n",
    "        def find(pre, N, K):\n",
    "            if N == 0:\n",
    "                res.append(pre)\n",
    "                return\n",
    "            temp = pre % 10\n",
    "            if temp - K >= 0:\n",
    "                find(pre*10+temp-K, N-1, K)\n",
    "            if temp + K <= 9:\n",
    "                find(pre*10+temp+K, N-1, K)\n",
    "            return\n",
    "        \n",
    "        for i in range(1, 10):\n",
    "            find(i, N-1, K)\n",
    "            \n",
    "        if N == 1:\n",
    "            res.append(0)\n",
    "            \n",
    "        return sorted(set(res))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N, K):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if N == 1:\n",
    "            return list(range(0, 10))\n",
    "        res = []\n",
    "        for i in range(1, 10):\n",
    "            if i + K < 10:\n",
    "                res.append([i, i + K])\n",
    "                \n",
    "            if i - K >= 0:\n",
    "                res.append([i, i - K])\n",
    "\n",
    "        if N == 2:\n",
    "            res = [int(''.join(str(n) for n in i)) for i in res]\n",
    "            return list(set(res))\n",
    "        \n",
    "        count = 2\n",
    "        def helper(res, N, K, count):\n",
    "            lst = []\n",
    "            for i in res:\n",
    "\n",
    "                if i[-1] + K < 10:\n",
    "                    tmp = i[::]\n",
    "                    tmp.append(i[-1] + K)\n",
    "                    lst.append(tmp)\n",
    "\n",
    "                if i[-1] - K >= 0:\n",
    "                    tmp = i[::]\n",
    "                    tmp.append(i[-1] - K)\n",
    "                    lst.append(tmp)\n",
    "               \n",
    "            count += 1\n",
    "            if count == N:\n",
    "                return lst\n",
    "            return helper(lst, N, K, count)\n",
    "            \n",
    "        res = helper(res, N, K, count)\n",
    "        res= [int(''.join(str(n) for n in i)) for i in res]\n",
    "        return list(set(res))\n",
    "\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "\n",
    "\n",
    "  def numsSameConsecDiff(self, N:int, K:int) -> List[int]:\n",
    "    if N == 1:\n",
    "        return list(range(0,10))\n",
    "\n",
    "    result = []\n",
    "    def collect_num(num:int ,prevd:int, N: int, diff: int):\n",
    "      num *= 10\n",
    "      digit = prevd + diff\n",
    "      if digit < 0 or digit > 9:\n",
    "        return\n",
    "      num += digit\n",
    "      if N == 1:\n",
    "        result.append(num)\n",
    "      else:\n",
    "        collect_num(num, digit, N -1, -diff)\n",
    "        if diff != 0:\n",
    "            collect_num(num, digit, N -1, diff)\n",
    "\n",
    "    start = list(range(1,10))\n",
    "    for d1 in start:\n",
    "        collect_num(d1,d1,N-1,K)\n",
    "        if K != 0:\n",
    "          collect_num(d1,d1,N-1,-K)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N, K):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ret = [i for i in range(1,10)]\n",
    "        if N==1 :\n",
    "            ret.append(0)\n",
    "        \n",
    "        for i in range(N-1):\n",
    "            del_list = []\n",
    "            add_list = []\n",
    "            for num in ret: \n",
    "                del_list.append(num) #将当前数字删除\n",
    "                last_num = num%10\n",
    "                if K==0:\n",
    "                    add_list.append(num*10+last_num)\n",
    "                else:\n",
    "                    if last_num+K < 10:\n",
    "                        add_list.append(num*10+last_num+K)\n",
    "                    if last_num-K >= 0:\n",
    "                        add_list.append(num*10+last_num-K)\n",
    "                    \n",
    "            for num in del_list:\n",
    "                ret.remove(num)\n",
    "                \n",
    "            for num in add_list:\n",
    "                ret.append(num)\n",
    "                \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N, K):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        rtype = []\n",
    "        if  N == 1:\n",
    "            return [x for x in range(10)]\n",
    "\n",
    "        temp_list = [-1 for i in range(N)]\n",
    "        index = 0\n",
    "        for j in range(1, 10):\n",
    "            temp_list[index] = j\n",
    "            if j >= K and K != 0:\n",
    "                self.dfs(index + 1, N, 0 - K, rtype, temp_list)\n",
    "            if 10 - j > K:\n",
    "                self.dfs(index + 1, N, K, rtype, temp_list)\n",
    "        return rtype\n",
    "\n",
    "    def dfs(self, index: int, N: int, K:int, rtype: List[int], temp_list: List[int]):\n",
    "        if index >= N:\n",
    "            return\n",
    "\n",
    "        temp_list[index] = temp_list[index-1] + K\n",
    "        if index == N - 1:\n",
    "            new_list = [str(x) for x in temp_list]\n",
    "            rtype.append(int(''.join(new_list)))\n",
    "            return\n",
    "\n",
    "        K =abs(K)\n",
    "        if 10 - temp_list[index] > K:\n",
    "            self.dfs(index + 1, N, K, rtype, temp_list)\n",
    "        if temp_list[index] >= K and K != 0:\n",
    "            self.dfs(index + 1, N, 0 - K, rtype, temp_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:\n",
    "        if N == 1:\n",
    "            return [0,1,2,3,4,5,6,7,8,9]\n",
    "        ans = []\n",
    "        for num in self.numsSameConsecDiff(N-1, K):\n",
    "            if num == 0:\n",
    "                continue\n",
    "            last = num % 10\n",
    "            if 0 <= last - K <= 9:\n",
    "                ans.append(num * 10 + last - K)\n",
    "            if K!=0 and 0 <= last + K <= 9:\n",
    "                ans.append(num * 10 + last + K)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:\n",
    "        ans = []\n",
    "        if N ==1:\n",
    "            ans.append(0)\n",
    "        def dfs(time,res):\n",
    "            if time >= N:\n",
    "                ans.append(int(res))\n",
    "                return \n",
    "            small = int(res[-1]) -K \n",
    "            big = int(res[-1])+K\n",
    "            if small >=0:\n",
    "                dfs(time+1,res+str(small))\n",
    "            if big <10 and big != small:\n",
    "                dfs(time+1,res+str(big))\n",
    "        for i in range(1,10):\n",
    "            dfs(1,str(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.rst = []\n",
    "\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        self.dfs(n, k, None)\n",
    "        return self.rst\n",
    "\n",
    "    def dfs(self, n, k, num):\n",
    "        if n == 0:\n",
    "            self.rst.append(num)\n",
    "            return\n",
    "        if num is None:\n",
    "            for i in range(1, 10):\n",
    "                self.dfs(n - 1, k, i)\n",
    "        else:\n",
    "            cur = num % 10 + k\n",
    "            if 0 <= cur < 10:\n",
    "                self.dfs(n - 1, k, num * 10 + cur)\n",
    "            \n",
    "            cur = num % 10 - k\n",
    "            if 0 <= cur < 10 and k != 0:\n",
    "                self.dfs(n - 1, k, num * 10 + cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        from collections import deque\n",
    "        nums = list(range(10))\n",
    "        start_q_list = list(range(1, 10))\n",
    "        q = deque(start_q_list)\n",
    "        while n > 1:\n",
    "            # print(len(q), q)\n",
    "            q_len = len(q)\n",
    "            for _ in range(q_len):\n",
    "                temp_val = q.popleft()\n",
    "                # print(temp_val)\n",
    "                for num in nums:\n",
    "                    if abs(num - temp_val%10) == k:\n",
    "                        new_val = temp_val*10 + num\n",
    "                        q.append(new_val)\n",
    "            n -= 1\n",
    "        # print(q)\n",
    "        return list(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [i for i in range(10)]\n",
    "        ret = []\n",
    "        def dfs(p, current):\n",
    "            if p == n:\n",
    "                ret.append(current)\n",
    "                return\n",
    "            last = current % 10\n",
    "            if last + k < 10:\n",
    "                dfs(p + 1, current * 10 + last + k)\n",
    "            if k != 0 and last - k >= 0:\n",
    "                dfs(p + 1, current * 10 + last - k)\n",
    "        n -= 1\n",
    "        for i in range(1, 10):\n",
    "            dfs(0, i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        def backtrace(index, curr, last):\n",
    "            if index > n:\n",
    "                res.append(curr)\n",
    "                return\n",
    "            up, down = last+k, last-k\n",
    "            if up < 10:\n",
    "                backtrace(index+1, curr*10+up, up)\n",
    "            if down >= 0:\n",
    "                backtrace(index+1, curr*10+down, down)\n",
    "\n",
    "        for i in range(1,10):\n",
    "            backtrace(2, i, i)\n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:\n",
    "        \n",
    "        tmp = []\n",
    "        rest = []\n",
    "        def dfs(i, val):\n",
    "            \n",
    "            tmp.append(val)\n",
    "\n",
    "            if i == N - 1:\n",
    "                \n",
    "                if len(tmp) > 0:\n",
    "                    if len(tmp) == 1:\n",
    "                        rest.append(tmp[:])\n",
    "                    else:\n",
    "                        if tmp[0] != 0:\n",
    "                            rest.append(tmp[:])\n",
    "\n",
    "                tmp.pop()\n",
    "                return\n",
    "\n",
    "            if 0 <= val + K <= 9:\n",
    "\n",
    "                dfs(i + 1, val + K)\n",
    "            \n",
    "            if 0 <= val - K <= 9:\n",
    "\n",
    "                dfs(i + 1, val - K)\n",
    "\n",
    "            tmp.pop()\n",
    "\n",
    "        \n",
    "        for i in range(0, 10):\n",
    "            dfs(0, i)\n",
    "        \n",
    "        final = []\n",
    "        for arr in rest:\n",
    "            final.append(int(''.join([str(x) for x in arr])))\n",
    "        \n",
    "        return list(set(final))\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:\n",
    "        if N == 1:\n",
    "            return [0,1,2,3,4,5,6,7,8,9]\n",
    "\n",
    "        self.res = []\n",
    "        @lru_cache(None)\n",
    "        def dfs(num):\n",
    "            if len(str(num)) == N:\n",
    "                self.res.append(num)\n",
    "                return\n",
    "            pre = num % 10\n",
    "\n",
    "            for i in range(10):\n",
    "                if abs(i - pre) == K:\n",
    "                    dfs(10 * num + i)\n",
    "            \n",
    "        for i in range(1, 10):\n",
    "            dfs(i)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, N: int, K: int):\n",
    "        if N == 1:\n",
    "            return [i for i in range(10)]\n",
    "        res, vis = set(), set()\n",
    "        def DFS(total, tmp):\n",
    "            if total == N:\n",
    "                res.add(tmp)\n",
    "                return\n",
    "            if tmp in vis:\n",
    "                return\n",
    "            t = int(tmp[-1])\n",
    "            if t + K < 10:\n",
    "                DFS(total+1, tmp+str(t+K))\n",
    "            if t - K >= 0:\n",
    "                DFS(total+1, tmp+str(t-K))\n",
    "            vis.add(tmp)\n",
    "        for i in range(1, 10):\n",
    "            DFS(1, str(i))\n",
    "        return [int(i) for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        self.res = []\n",
    "        for d in range(1, 10):\n",
    "            self.helper(n-1, k, [d])\n",
    "        return self.res\n",
    "    \n",
    "    def helper(self, n, k, path):\n",
    "        if n == 0:\n",
    "            self.res.append(int(\"\".join(map(str, path))))\n",
    "            return\n",
    "\n",
    "        last1 = path[-1] - k\n",
    "        if last1 >= 0:\n",
    "            self.helper(n-1, k, path + [last1])\n",
    "        last2 = k + path[-1]\n",
    "        if last2 < 10 and last2 != last1:\n",
    "            self.helper(n-1, k, path + [last2])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(1, 10):\n",
    "            self.find(n, k, str(i), result)\n",
    "        return result\n",
    "\n",
    "    def find(self, n, k, num_str, result):\n",
    "        if len(num_str) == n:\n",
    "            result.append(int(num_str))\n",
    "            return\n",
    "        last_digit = int(num_str[-1])\n",
    "        if last_digit + k <= 9:\n",
    "            self.find(n, k, num_str + str(last_digit + k), result)\n",
    "        if k != 0 and last_digit - k >= 0:\n",
    "            self.find(n, k, num_str + str(last_digit - k), result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:      \n",
    "        res = []\n",
    "        def dfs(res, cnt, cur):\n",
    "            if cnt == 1:\n",
    "                res.append(cur)\n",
    "                return \n",
    "            tail = cur % 10\n",
    "            if tail + k <= 9:\n",
    "                dfs(res, cnt - 1, cur * 10 + tail + k)\n",
    "            if tail - k >= 0 and k != 0:\n",
    "                dfs(res, cnt - 1, cur * 10 + tail - k)\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            dfs(res, n, i)\n",
    "\n",
    "        return res\n",
    "\n",
    "        # res = list(range(1,10))\n",
    "        # for i in range(n-1):\n",
    "        #     tmp = []\n",
    "        #     while len(res) > 0:\n",
    "        #         a = res.pop(0)\n",
    "        #         tail = a % 10\n",
    "        #         if tail + k <= 9:\n",
    "        #             tmp.append(a * 10 + tail + k)\n",
    "        #         if tail - k >= 0 and k != 0:\n",
    "        #             tmp.append(a * 10 + tail - k)\n",
    "        #     res = tmp\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        temp = ''\n",
    "        if k == 0:\n",
    "            result = [str(i) * n for i in range(1, 10)]\n",
    "            return [int(x) for x in result]\n",
    "        def createNum(pre, m, k):\n",
    "            if m == 0:\n",
    "                ans.append(int(pre))\n",
    "            else:\n",
    "                if pre == '':\n",
    "                    for i in range(1, 10):\n",
    "                        pre = pre + str(i)\n",
    "                        createNum(pre, m-1, k)\n",
    "                        pre = pre[:-1]\n",
    "                else:\n",
    "                    t = int(pre[-1])\n",
    "                    if t >= k:\n",
    "                        newpre = pre + str(t - k)\n",
    "                        createNum(newpre, m - 1, k)\n",
    "                    if t + k < 10:\n",
    "                        newpre = pre + str(t + k)\n",
    "                        createNum(newpre, m - 1, k)\n",
    "        createNum('', n, k)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        def backtrack(tmp, ):\n",
    "            if len(tmp) == n :\n",
    "                 res.add(int(tmp))\n",
    "                 #print(tmp)\n",
    "                 return\n",
    "            last = int(tmp[-1])\n",
    "            up, down = last + k, last - k \n",
    "            if up >= 0 and up < 10 :\n",
    "                tmp += str(up % 10)\n",
    "                backtrack(tmp)\n",
    "                tmp = tmp[:-1]\n",
    "            if down >= 0 and down < 10 :\n",
    "                tmp += str(down % 10)\n",
    "                backtrack(tmp)\n",
    "                tmp = tmp[:-1]\n",
    "        res = set()    \n",
    "        for i in range(1, 10) :\n",
    "            backtrack(str(i))\n",
    "        #print(res)\n",
    "        return sorted(list(res), reverse = False)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def helper(i,num):\n",
    "            if i == n-1:\n",
    "                return [str(num)]\n",
    "            if num+k<10:\n",
    "                nxt1 = helper(i+1,num+k)\n",
    "            else:\n",
    "                nxt1 = []\n",
    "            if k!=0 and num-k>=0:\n",
    "                nxt2 = helper(i+1,num-k)\n",
    "            else:\n",
    "                nxt2 = []\n",
    "            res = []\n",
    "            for i in nxt1:\n",
    "                res.append(str(num)+i)\n",
    "            for i in nxt2:\n",
    "                res.append(str(num)+i)\n",
    "            return res\n",
    "        res = []\n",
    "        for i in range(1,10):\n",
    "            cur = helper(0,i)\n",
    "            res +=cur\n",
    "\n",
    "        return [int(i) for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\r\n",
    "        ans = list(range(1, 10))\r\n",
    "        while ans[0] < 10**(n-1):\r\n",
    "            x = ans.pop(0)\r\n",
    "            left = x % 10 - k\r\n",
    "            right = x % 10 + k\r\n",
    "            if left >= 0:\r\n",
    "                ans.append(x * 10 + left)\r\n",
    "            if left != right and right <= 9:\r\n",
    "                ans.append(x * 10 + right)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        res = list()\n",
    "        def dfs(cur, left):\n",
    "            if left == 0:\n",
    "                res.append(cur)\n",
    "            else:\n",
    "                last = cur % 10\n",
    "                if last + k < 10:\n",
    "                    dfs(cur * 10 + last + k, left - 1)\n",
    "                if k > 0 and last - k >= 0:\n",
    "                    dfs(cur * 10 + last - k, left - 1)\n",
    "        for i in range(1, 10):\n",
    "            dfs(i, n - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:\n",
    "        cur_level = {i for i in range(1, 10)}\n",
    "        for _ in range(n - 1):\n",
    "            next_level = set()\n",
    "            for num in cur_level:\n",
    "                digit = num % 10\n",
    "                if digit - k >= 0:\n",
    "                    next_level.add(10 * num + digit - k)\n",
    "                if digit + k < 10:\n",
    "                    next_level.add(10 * num + digit + k)\n",
    "            cur_level = next_level\n",
    "        if n == 1:\n",
    "            cur_level.add(0)\n",
    "        return list(cur_level)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
